Internet Info 1994 March

home *** CD-ROM | disk | FTP | other *** search

/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / ien / ien-178 < prev next >

Wrap

Text File | 1988-12-01 | 38.9 KB | 1,240 lines

IEN 178 April 1981 ADDRESSING PROBLEMS IN MULTI-NETWORK SYSTEMS Carl A. Sunshine University of Southern California Information Sciences Institute 4676 Admiralty Way Marina del Rey, CA 90291 Abstract To allow uers in different networks to communicate with each other, development of powerful yet practical naming, addressing, and routing facilities is essential. Basic procedures for multi-network systems under control of a single organization have begun to be used, but a large set of more sophisticated goals remain to be addressed. This paper describes several of these more advanced problems including extendability, multihoming, network partitioning, mobile hosts, shared access, local site connections, gateway routing, and overcoming differences in heterogeneous systems. Note: There are three figures associated with this document which may be obtained from the author by sending a message to <SUNSHINE@ISIF>. -1- Introduction The interconnection of multiple computer networks makes it possible for ever wider communities of computer users and applications to interact with each other. A basic set of problems that must be solved in accomplishing such interconnections concerns providing naming, addressing, and routing procedures that are general and convenient yet practical. These problems are particularly difficult when networks of different designs and/or operating under different authorities must be interconnected. Current multi-network systems are fairly small (tens of networks maximum) and largely designed by and under control of a single organization. (We shall call this "homogeneous" internetworking.) Basic interconnection is supported by simple hierarchical addressing and routing procedures employed uniformly throughout the system [1,4,10,13]. Interconnections of different multi-network systems (heterogeneous internetworking) are just beginning to be made, largely by ad hoc means. Thus, while some of the basic problems have been solved, a large set of secondary problems will soon be upon us. These include problems of scale (current methods are impractical for systems with hundreds or thousands of networks); supporting more sophisticated functions such as multihoming, network -2- partitioning, mobile hosts, and shared access; and overcoming the different procedures in heterogeneous systems. This paper describes several of these interesting problems, and discusses potential solutions. The emphasis is on developing a feel for the range of problems and solutions rather than on detailed or formal treatment of any one problem. In many cases it will be clear that further research is needed to clarify the problems or to develop and evaluate better solutions. Hierarchical Methods A basic approach to addressing and routing in large systems is to use hierarchical methods. These methods can be applied at various levels (e.g., within networks and among networks). We give a brief summary of the basic principles involved since these form the background for many of the other problems. As the number of subscribers or "hosts" in a single network increases, it becomes desirable to introduce a number of switches, each serving a subset of the hosts. These switches must maintain routing tables which give the best outgoing link (or set of links) for any destination. The tables are used to forward incoming packets properly toward their destination. In datagram networks, a routing decision based on final destination is made for every packet, while in virtual circuit nets only the initial call request packet -3- requires the full routing decision (subsequent packets of a call are forwarded over fixed routes kept in other tables). If every switch maintained routing information for every destination individually, the routing tables would become very large. A standard approach is to introduce hierarchical addressing, where each host is assigned a particular port on a particular switch, and hence addresses take the form <switch, port>. Then routing may also be done hierarchically by sending all packets destined to a given switch over the same route, ignoring the "low order" portion of the address. Hence each switch need only maintain routes to other switches, greatly reducing the number of different destinations, and hence entries, in the routing tables. Note that hierarchical routing is one major motivation for introducing hierarchical addresses, but these two techniques do not necessarily go together as we shall see below. Another reason for hierarchical addresses is simply to distribute the authority for assigning addresses within a large system [14]. The same techniques may be extended to multi-network systems by adding another level to the addressing hierarchy so that addresses take the form <net, switch, port>. With hierarchical routing, packets are first routed to the destination network, ignoring the rest of their address, and then routed within the final network as above. This form of -4- hierarchical addressing has been adopted by the public packet switching networks in CCITT Recommendation X.121, and it appears that most public networks intend to use hierarchical routing as well [13,19]. The reduction of routing table size that accompanies hierarchical routing has its price. The resulting routes may not always be optimal. If there are two ways to reach a remote network (as is often the case), one may be better for some hosts within that network and the other for other hosts. But there is by design no way to determine this from a local routing table which carries a single entry for the entire remote network. An even more serious consequence of strict hierarchical routing is discussed in the next section. To avoid these problems, routing decisions may based on more of the address where desirable [5,14]. For example, an internetwork routing table could be augmented with entries for individual switches receiving high traffic in a remote network, while other switches in that network were covered by a single network level entry. This leads to a selective increase in the size of routing tables, and requires the ability to search the tables for variable length portions of addresses and to update tables with varying levels of detail. Network Partitions A network is said to be partitioned when enough links and/or switches fail so that two or more subsets of its hosts -5- are formed which cannot communicate with each other. In an isolated network there is no remedy for this situation until sufficient repairs are made to restore connectivity. But if the partitioned net is part of a multi-network system, there may be paths through other nets which could connect the partitions. Unfortunately, these paths are not used within the strictly hierarchical routing procedures described above. And even if a "local" packet were sent to a neighboring network by a switch, it would likely be routed right back into the same paritition by the other network. This last point indicates another difficulty. Traffic in a remote network destined for the partitioned net will be routed into one or the other partition without consideration of its within-network switch. (Remember that other networks see a single best route to this network considered as a whole.) For some destinations, this will be the wrong partition and the destination will be unreachable by internal routes, leading to failure to deliver packets routed that way from remote nets [14,16]. One solution to this problem is to configure the system with sufficient robustness that partitions occur very rarely, and to simply tolerate the above delivery problems when they occur. This may be satisfactory for commercial systems where loads and outages are fairly predictable. In military systems where numerous disruptions are -6- anticipated, some means of forcing use of any available connectivity is desirable [3]. One approach is to treat the number of networks as dynamic, and turn a partitioned network into two networks, each of which can be an explicit destination. This requires rather complex methods of updating each network's view of the overall topology, and promulgates knowledge of a partition in one network to all other networks [8]. Another approach might be to return a special error message to the neighboring router forcing it to choose another entry point to the failed network. This backup-and-try-alternate method has been implemented for call setup in Telenet [19]. "Fast Track" Routing It is not only in case of catastrophic events like partitioning that use of external routes between two points within the same region may be desirable. If two networks cover the same geographical area, for example a store-and-forward ground net and a broadcast satellite net, performance for some types of traffic may be improved by exiting the ground net near the source, going through the satellite net, and returning to the ground net near the destination. File transfer traffic might obtain higher throughput in this fashion, for example. To accomplish this, it is once again necessary to violate hierarchical routing. Either the network level routing must -7- distinguish between destinations best reached directly within the network and those best reached by going outside, or the within-network level must be made to view paths through other networks as a special kind of internal link that is available [9]. But in the latter case, the network level path status information must be brought into the internal link status maintenance procedures, probably a messy business. Multihoming A subscriber may want to have multiple connections to a communication system for reliability or performance reasons. In the simplest case, several independent physical lines may be managed as one logical data link to obtain greater reliability, higher throughput, or lower cost (due to the idiosyncracies of carrier tariffs). Several such multiline procedures have been developed, for example in Transpac, and in X.75. The subscriber still has a single address, and no further complications are involved. In order to protect against node failures as well as line failures, lines to different switches must be used. In this case the user has two (or more) different addresses. The multiple addresses may be at any level in the address hierarchy: (e.g. two addresses within a network, or connected to two different nets). Multiple lines may also provide better performance by connecting directly to highly used areas -8- of the system and thus avoiding extra hops through the network. In order to obtain these benefits, the ability to use both addresses and to select the optimal address must exist. This may be accomplished by the source explicitly selecting one address. But this requires the source to know that there are multiple addresses for a given destination, to select the best address for performance, and to switch to an alternate after a failure. These admittedly weighty burdens could be aided by a remote directory/routing service. Alternatively, the packet could carry the multiple addresses explicitly, allowing each switch to pick the best of the best routes for each address. This of course adds to packet length and routing processing load. Instead of carrying the multiple addresses, the packet might carry the name (or "logical address") of the destination [14], leaving it for the switches to lookup and select the best address at each point. This would reduce packet complexity, but increase the switch processing demands even further. Thus we have a spectrum from high source effort to high network effort in making use of multiple addresses. In datagram nets it is probably impractical to require complex processing of the address on every packet, so more source effort will probably be required. In virtual circuit nets a -9- greater amount of effort can be expended by the net on the call setup request. Some public nets are already providing call forwarding facilities where a call to one inoperative or busy address will automatically be forwarded to an alternate address. There are problems at the destination as well as the source. To obtain the benefits of multihoming, the destination must be willing to accept traffic on all addresses. In virtual circuit nets, all the traffic for a given call must flow over the same line, so a failure during the call cannot be recovered by using an alternate address. The call must be cleared with possible loss of data, and a new one requested. Even in some datagram nets, higher level protocols are sensitive to the addresses of the local and remote hosts [3]. The source address is used to demultiplex incoming packets to the proper "connection," and packets coming from an alternate address from that used to establish the connection would not be recognized properly. To avoid this problem, the (single) name of the source could be used in the connection tables, but this would have to be carried in the packet. Alternatively, the multiple remote addresses could be stored as part of the connection table so that a packet specifying any one as source would match properly. These multiple addresses would have to be supplied as part of the connection establishment, and might -10- be profitably used in sending traffic if the original address failed. Mobile Hosts Mobile hosts represent a special case of the multiple address problem. Of course all hosts are technically mobile in the sense that they occasionally change their address due to reconfiguration and movement within the user organization, or modifications to the network topology. Hence directory information to associate the name of a host with its current address is available in most systems, either locally or via some remote server. However, the problem of changing addresses becomes qualitatively different when the host is expected to change its network attachment point frequently, even in the midst of previously established connections. Special dynamic routing and addressing procedures have been developed for ground based mobile hosts communicating via packet radio within a single network [6]. As distances are increased and this technology is transferred to airplanes, crossing network boundaries may also be anticipated. One method for "tracking" mobile hosts would be to maintain a specialized database of their current locations (perhaps replicated for reliability), as is done within individual packet radio nets (by the "station"). The mobile hosts would send updates to this database as needed, and users -11- wishing to establish communication could query the database much as any other directory service. However, they should be prepared to receive frequent address change notifications in the course of a connection, either from the mobile host itself, alternate relay points, or the database. Further details of such a scheme may be found in [18]. Assuming traffic reaches them, destinations must still be "desensitized" from the particular source address as discussed above, since this will change. But there is no fixed set of alternates to exchange at connection setup time in this case, so packets probably must carry a unique identifier (name) of the source as well as its current address. For reliability purposes, they should probably also carry the name of the destination in case it is no longer associated with the address they reach. Mobile hosts may have multiple addresses at one moment as well as at different times (e.g., an aircraft may be in contact with two radio nets). Thus it becomes apparent that problems can interact with each other, making solutions more difficult. Sharing Network Access The opposite problem to one host having several access lines to the net is several hosts sharing a single access line. This may be desirable where the number of physiscal interfaces or ports to the network is limited, or to share a -12- long access line among nearby subscribers. Public networks provide multidrop interfaces for terminal traffic (X.28), but not for packet mode traffic (X.25). For packet level devices, the alternative to providing a fixed and hence inefficient frequency or time division multiplexor must be some sort of "intelligent" multiplexor functioning at the packet level of network access protocols. Broadcast networks (e.g., Ethernets and ring nets) inherently provide this capability since every interface hears all traffic. Each interface is responsible for accepting appropriate traffic, and can sometimes be set to intercept traffic for multiple addresses. Another approach is to use a higher level of protocol to provide the necessary demultiplexing. The Arpanet access (Host-IMP) protocol does not allow for shared interfaces, and the limitation of 4 host interfaces on the original IMPs has proved troublesome in some cases. The Internet Protocol (IP) is the next level above particular network access protocols in the ARPA hierarchy [10,11]. IP addresses are sufficiently long to support multiple "logical" hosts at the same physical host port on the Arpanet. The Host-IMP header indicates the same physical host address for all such packets, and the higher level IP module at the destination demultiplexes the packets to the correct logical host. An independent device to perform this function has been developed based on PDP-11/03 -13- hardware. This "port expander" effectively turns each IMP port into 4-8 ports for hosts that use the Internet Protocol [7]. Networks vs. Gateways as Switches In most models of hierarchical routing, networks are assumed to function as "super-switches," just as switching nodes do within one network. This view would be literally true if there were a single internet switching node in each net to which all incoming traffic from other nets was routed, and which then forwarded the traffic to another network or to a local host. Figure X shows a small example of a multi-network system and a routing table at one network/switch. The routing table gives the cost in internet hops and the best neighbor net to use to reach each other network in the system. For efficiency, this internet switching function is usually distributed to processors called "gateways" serving each of the internet links. Instead of being sent through the net to some central point, the internet traffic can be routed immediately at its entry point to the best exit point (either another gateway or the destination host). Figure Y shows the same internet system with internet links labeled, and a routing table at the gateway located on one incoming link. Since the gateway must send packets across its net to a -14- particular outgoing link, the routing table now shows the name of this next link rather than the next net. Another step in this progression leads to a single gateway located in the "middle" of each internet link rather than two separate processors in each net. The gateways take on the identity of their internet link(s). In this configuration, it is more realistic to count the network hops as the cost fucntion rather than the internet links. Hence each gateway is maintaining a distance (in network hops) between gateways, and a best next gateway to use for each destination. In this model, the gateways may be more realistically viewed as the switching nodes, and the networks as the links connecting them. This is essentially the dual of the earlier model as shown in Figure Z. But the destinations in the routing table are networks, not gateways, making this a curious sort of hybrid scheme. Hence it is not clear how to apply the "link state" type of routing procedures used in single networks (e.g., the Arpanet) to this multi-network configuration with gateways as switching nodes. Local Site Connections Many sites start with a single host connected to a long-haul net. As the site develops, a few more hosts are connected, also directly to the long-haul switch. As even more hosts want to join the net at that site, problems result from costly or inefficient use of network access procedures. -15- Some sort of port expander or intelligent multiplexor devices as discussed above become attractive. This addresses the network connection problem, but not the local traffic requirements which are also growing, and may easily exceed traffic to remote sites. The network switch is handling a lot of traffic that never goes any further through the net. In some cases the port expanders may be capable of local switching, forming a rudimentary local net. To handle local traffic more efficiently, an explicit local net may be desirable. A question then arises as to whether this net should be "known" to the rest of the internet system, and connected to it via one or more full-fledged gateways, or whether it should be "invisible" at the internet level with its hosts appearing as if they were directly connected to the long-haul net. In the first case, local hosts have internet addresses on an explicit local net, while in the second they have addresses on the long-haul net. The explicit local net approach has certain advantages stemming from the explicit identification of the group of hosts at a site as a network. If the site is connectected to two or more other nets, then the internet routing mechansims will automatically choose the best path to the local hosts, which have only a single address (on their local net). However, this participation at the internet level can also be a problem. As the number of sites with local nets -16- increases, so will the number of nets and hence the size of the routing tables and updates which must be propagated all over the internet system. If the growth continues at a site so that there are several local nets connected by "local" gateways, should all of these nets and the local topology be known throughout the internet system? At some point treating local nets on a par with long-haul or backbone nets breaks down. The invisible local net approach, on the other hand, avoids problems of proliferating networks at the internet level. Many port expander or local distribution systems can perform an internal switching function, relieving the long-haul net switch of handling local traffic. But sites with connections to two or more nets will have multiple addresses for their hosts (one for each net the hosts appear "directly" connected to), and this causes some difficulties as discussed above under Multihoming. The best solution to this tradeoff is not clear. Adding an additional level to the addressing hierarchy may be a temporary solution, but it, too, will become strained in time. This suggests allowing a variable number of levels in the addressing hierarchy, adding new levels as complexity increases in some area. But this imposes a rigid ordering of levels and hence routing, while in reality "higher" and "lower" may depend on the viewpoint of the user. Further -17- research is needed on how internet systems may grow and still maintain efficient addressing and routing procedures. Multiple Domains Most of the previous discussion has assumed a single compatible "domain" in which network addressing and routing procedures are carried out uniformly. In the real world we have already seen the growth of several large domains with different conventions, including public, mainframe manufacturer, Defense Department, and local networks. It is unrealistic and perhaps impossible that these diverse groups will ever adopt a single addressing scheme, so we must live with the problem of multiple domains for the foreseeable future. One approach is to assume that one domain will make use of another merely as transport medium between its own homogeneous components. The used system appears merely as one of several types of media that the using system can employ via appropriate access protocols. The using system's packets will be "encapsulated" in the used system's protocols. Of course the two domains can make use of each other, achieving coexistence, if not complete interoperation, by "mutual encapsulation" [15]. To achieve full interoperability between heterogeneous systems, each system must recognize the hosts on the other. -18- Two basic choices are possible for crossing domain boundaries: mapping and source routing. In the mapping approach, each domain provides a set of otherwise unused internal addresses which it maps to particular addresses in other domains. Traffic addressed to one of these "pseudo-addresses" is routed to an interface or gateway to the appropriate other domain, at which point the pseudo-address is converted into an address in the other domain. In the simplest case, this requires only bilateral agreements between domains, but it may also be extended across intermediaries with further collaboration. A disadvantage of this approach is that the number of external addresses available is limited to those for which mappings have been previously defined and installed. Typically only a small fraction of remote parties are supported. Another disadvantage is that the same party has different addresses in different domains--the directory of names to addresses has many entries for each name, one for each domain supporting that party. The major advantage is that for those names supported, the users may address remote parties in exactly the same fashion as local ones, with no additional procedures. In source routing [14,17,5], the source specifies a route to reach the destination consisting of the addresses of successive inter-domain gateways, and ending with the final -19- destination. Each address in this list is interpreted within a domain where it is meaningful, and then removed so that the next address is available in the next domain transitted. Using this method, the full range of remote parties is accessable, and the inter-domain gateways do not have to maintain any predefined mappings or perform address conversions. The burden is shifted to the source which must know enough about the overall topology and address formats to construct a successful source route. Of course packet headers become bigger, and packet processing increases to accomodate the variable length source routes. Once again, the "address" of a given party varies from one domain to another, but it is now possible to combine this information--if the directory gives the source route to X from domain A, and a user in domain B knows a route to domain A, he can concatenate them to get a route to X from B (although it may not be an optimal route). It is often useful to collect a return route at the same time the source route is being consumed. This allows the destination to reply. In general the return route is not simply the inverse of the source route. The return addresses are added as the packet enters each domain, while the successive destination addresses are removed as the packet exits each domain (see [17] for a detailed example). The "network independent" transport protocol [2] -20- developed by the British PSS Users Forum is one of the first to explicitly deal with the problem of multiple domains. They suggest essentially a source routing mechanism. There are additional provisions for translating explicitly identified address information transmitted as data between end users. The protocol assumes a route setup procedure as part of call establishment so that the source route need only be carried in the call request packet. The public networks have also provided for a limited form of source routing in the Call User Data field of X.25 call request packets. This field may be used by the destination DTE as additional address information for subsequent steps in a call. This mechanism was used to allow international calls between Canadian and US public networks before the hierarchical X.121 numbering plan was put into effect [12]. The Call User Data field is also beginning to be used in an ad hoc fashion to provide addressing within various private and/or local nets connected to public nets. The Arpa Internet Protocol also supports a source routing option, but addresses within the route are all expected to be IP format addresses [11]. Conclusions We have identified a number of problems that must be considered in going beyond the simple network interconection techniques that are in use today. The significance of these -21- problems is just beginning to be widely percieved. Some preliminary solutions have been proposed, but little practical experience exists. Much work remains to be done in clarifying the problems, and in developing and evaluating solutions. Acknowledgements Many of the concepts presented in this paper have been discussed over several years as part of the ARPA Internet project. Much of the credit for developing and clarifying these ideas belongs to my colleagues at ISI and the other sites engaged in this project. References Note: Several of the references listed below are Internet Experiment Notes, unpublished memos written for the ARPA Internet project. [1] D. R. Boggs, J. F. Shoch, E. A. Taft, and R. M. Metcalfe, "Pup: An Internetwork Architecture," IEEE Trans. on Communications 28, 4, April 1980, pp. 612-623. [2] British Post Office PSS User Forum, A Network Independent Transport Service, February 1980. [3] V. G. Cerf, Internet Addressing and Naming in a Tactical Environment, Internet Experiment Note 110, August 1979. [4] V. G. Cerf and P. T. Kirstein, "Issues in Packet-Network Interconnection," Proc. IEEE 66, 11, November 1978, pp. 1386-1408. [5] D. D. Clark and D. Cohen, A Proposal for Addressing and Routing in the Internet, Internet Experiment Note 46, June 1978. [6] R. E. Kahn, S. A. Gronemeyer, J. Burchfiel, and R. C. Kunzelman, "Advances in Packet Radio Technology," Proc. IEEE 66, 11, November 1978, pp. 1468-1496. -22- [7] H. A. Nelson, J. E. Mathis, and J. M. Lieb, The ARPANET IMP Port Expander, SRI Report 1080-140-1, November 1980. [8] R. Perlman, Flying Packet Radios and Network Partitions, Internet Experiment Note 146, June 1980. [9] R. Perlman, Utilizing Internet Routes as Expressways Through Slow Nets, Internet Experiment Note 147, June 1980. [10] J. B. Postel, "Internetwork Protocol Approaches," IEEE Trans. on Communications 28, 4, April 1980, pp. 604-611. [11] J. B. Postel, C. A. Sunshine, and D. Cohen, "The ARPA Internet Protocol," to appear in Computer Networks, 1981. [12] A. M. Rybczynski, D. F. Weir, and I. M. Cunningham, "Datapac Internetworking for International Services," Proc. 4th Int. Conf. on Computer Communication, September 1978, pp. 47-56. [13] A. M. Rybczinski, J. D. Palframan, and A. Thomas, "Design of the Datapac X.75 Internetworking Capability," Proc. 5th Int. Conf. on Computer Communication, October 1980, pp. 735-740. [14] J. F. Shoch, "Inter-Network Naming, Addressing, and Routing," Proc. 17th IEEE Computer Society Int. Conf., September 1978, pp. 72-79. [15] J. F. Shoch, D. Cohen, and E. A. Taft, "Mutual Encapsulation of Internetwork Protocols," to appear in Computer Networks, 1981. [16] C. A. Sunshine, "Interconnection of Computer Networks," Computer Networks 1, 3, January 1977, pp. 175-195. [17] C. A. Sunshine, "Source Routing in Computer Networks," ACM SIGCOMM Computer Communication Rev. 7, 1, January 1977, pp. 29-33. [18] C. A. Sunshine and J. B. Postel, Addressing Mobile Hosts in the ARPA Internet Environment, Internet Experiment Note 135, March 1980. [19] D. F. Weir, J. B. Holmblad, and A. C. Rothberg, "An X.75 Based Network Architecture," Proc. 5th Int. Conf. on Computer Communication, October 1980, pp. 741-750.